package LeetCode;

import java.util.HashMap;
import java.util.Map;

public class LC_149_MaxPointsonaLine {

    public static void main(String[] args) {

    }

    class Point {
        int x;
        int y;

        Point() {
            x = 0;
            y = 0;
        }

        Point(int a, int b) {
            x = a;
            y = b;
        }
    }

    static class Solution {
        public int maxPoints(Point[] points) {
            if (points == null) return 0;
            if (points.length <= 2) return points.length;
            Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
            int res = 0;
            int max;
            int overLap;
            for (int i = 0; i < points.length - 1; i++) {
                map.clear();
                overLap = 0;
                max = 0;
                for (int j = i + 1; j < points.length; j++) {
                    int x = points[j].x - points[i].x;
                    int y = points[j].y - points[i].y;
                    if (x == 0 && y == 0) {
                        overLap++;
                        continue;
                    }
                    int gcd = generateGCD(x, y);
                    if (gcd != 0) {
                        x = x / gcd;
                        y = y / gcd;
                    }
                    if (map.containsKey(x)) {
                        if (map.get(x).containsKey(y))
                            map.get(x).put(y, map.get(x).get(y) + 1);
                        else
                            map.get(x).put(y, 1);
                    } else {
                        Map<Integer, Integer> temp = new HashMap<>();
                        temp.put(y, 1);
                        map.put(x, temp);
                    }
                    max = Math.max(max, map.get(x).get(y));
                }
                res = Math.max(res, max + overLap + 1);
            }
            return res;
        }

        private int generateGCD(int x, int y) {
            if (y == 0)
                return x;
            return generateGCD(y, x % y);
        }
    }

}